'''
https://leetcode.cn/problems/binary-tree-level-order-traversal/
'''
from typing import Optional, List
from collections import deque

from c06_tree.utils import TreeNode, built_tree_by_complete_tree


class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root: return []
        q = deque([root])
        res = []
        level = []
        end, next_end = root, None
        while q:
            cur = q.popleft()
            level.append(cur.val)
            if cur.left:
                q.append(cur.left)
                next_end = cur.left
            if cur.right:
                q.append(cur.right)
                next_end = cur.right
            if cur == end:
                res.append(level[:])
                level = []
                end = next_end
        return res

    # 还是一样的思路，只不过在遍历q的时候，上边是通过两个变量控制一层是否结束，这里是一次那一层
    def levelOrder2(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root: return []
        q = deque([root])
        res = []
        while q:
            level = []
            level_size = len(q)
            for i in range(level_size):
                cur = q.popleft()
                level.append(cur.val)
                if cur.left:
                    q.append(cur.left)
                if cur.right:
                    q.append(cur.right)
            res.append(level)
        return res


arr = [3,9,20,None,None,15,7]
root = built_tree_by_complete_tree(arr)
ans = Solution().levelOrder(root)
print(ans)







